package newcoder.算法.归并排序;

/**
 * 归并排序
 * 包括，两路归并排序，多路归并排序，可用于内排序，也可以用于外排序
 * 归并排序是一种稳定的排序
 *
 * @Author Mr.wang
 * @Description 将两个（或两个以上）有序表合并成一个新的有序表，
 * 即把待排序序列分为若干个子序列，每个子序列都是有序的，然后再把有序子序列合并为整体有序序列；
 * <p>
 * 两路归并排序算法思路：
 * 分而治之（divide-conquer），每个递归过程涉及三个步骤
 * 1. 分解：把待排序的n个元素的序列分解成两个子序列，每个子序列，包括n/2个元素；
 * 2. 治理：对每个子序列分别调用归并排序MergerSort，进行递归操作；
 * 3. 合并：合并两个排好序的子序列，生成排序结果。
 * @Date 2020-04-11
 */
public class Main {

    /**
     * @param nums
     * @param low
     * @param high
     * @return
     */
    public static int[] sort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            sort(nums, low, mid);
            sort(nums, mid + 1, high);
            merge(nums, low, mid, high);
        }
        return nums;
    }


    public static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 把右边剩余的数移入数组
        while (j < high) {
            temp[k++] = nums[j++];
        }

        // 把新数组中的数覆盖nums数组
        for (int l = 0; l < temp.length; l++) {
            nums[l + low] = temp[l];
        }

    }

}
